#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <algorithm>

using namespace std;

#define NULO 0
#define FALSE 0
#define TRUE 1

typedef struct Enlace{
	int primer_servidor;
	int segundo_servidor;
	int costo;
} Enlace;

typedef struct Nodo{
	Nodo *proximo;
	Nodo *final_lista;
	Nodo *raiz;
	int cantidad_de_elementos;
} Nodo;

typedef struct NodoArbol{
		int numero;
		int grado;
		bool estoyEliminado;
		list<int> adyacencias;
} NodoArbol;

void leerStdin();
list<Enlace> armar_servidor(vector<Enlace> enlaces, int cantEnlaces, int cantServidores);
bool trd_order(Enlace e1, Enlace e2);
ostream& operator<<(ostream &os, pair<list<Enlace>, int>);
int elegir_raiz(list<Enlace> aristas, int cantServidores);

int main(int argc, char *argv[]) {
	leerStdin();
	return 0;
}

void leerStdin() {
	while(1){
		/* Leer instancia */
		int cantServidores(0);
		int cantEnlaces(0);
		vector<Enlace> enlaces(cantEnlaces);
		Enlace enlace;

		cin >> cantServidores;

		if(cantServidores == 0) break;
				
		cin >> cantEnlaces;

		for(int i = 0; i < cantEnlaces; i++) {
			cin >> enlace.primer_servidor;
			cin >> enlace.segundo_servidor;
			cin >> enlace.costo;
			enlaces.push_back(enlace);
		}

		list<Enlace> res = armar_servidor(enlaces, cantEnlaces, cantServidores);

		int master = elegir_raiz(res, cantServidores);
		
		pair<list<Enlace>, int> respuesta;
		respuesta.first.swap(res);
		respuesta.second = master;
		
		cout << respuesta;
		
	}
}

list<Enlace> armar_servidor(vector<Enlace> enlaces, int cantEnlaces, int cantServidores) {
	int primer_serv;
	int segundo_serv;
	
	list<Enlace> resultado;
	
	Nodo *raiz1;
	Nodo *raiz2;
	Nodo *raizAux;
	Nodo *nodoAux;
	
	make_heap(enlaces.begin(), enlaces.end(), trd_order);
	Nodo* servidores[cantServidores];
	
	for(int i = 0; i < cantServidores; i++) {
		Nodo *nodo_servidor = new Nodo;
		nodo_servidor->proximo = NULO;
		nodo_servidor->final_lista = nodo_servidor;
		nodo_servidor->raiz = nodo_servidor;
		nodo_servidor->cantidad_de_elementos = 1;
		
		servidores[i] = nodo_servidor;
	}
	
	for (int k = 0; k < cantEnlaces; k++) {
		//Levanto un enlace
		primer_serv = enlaces.front().primer_servidor;
		segundo_serv = enlaces.front().segundo_servidor;
		
		primer_serv--;
		segundo_serv--;
		
		//Chequeo si no formo un ciclo
		if(servidores[primer_serv]->raiz != servidores[segundo_serv]->raiz) {
		
			raiz1 = servidores[primer_serv]->raiz;
			raiz2 = servidores[segundo_serv]->raiz;
			
			//Me fijo cual es la de longitud más corta	
			if(raiz1->cantidad_de_elementos < raiz2->cantidad_de_elementos) {
				raizAux = raiz1;
				raiz1 = raiz2;
				raiz2 = raizAux;
			}
			
			//Pongo la lista más pequeña atrás de la más grande y actualizo la raiz de la más grande
			(raiz1->final_lista)->proximo = raiz2;
			raiz1->final_lista = raiz2->final_lista;
			raiz1->cantidad_de_elementos += raiz2->cantidad_de_elementos; 
			
			nodoAux = raiz2;
			
			//Actualizo los elementos de la lista más pequeña que estoy agregando
			for(int h = 0; h < raiz2->cantidad_de_elementos; h++) {
				nodoAux->raiz = raiz1;
				nodoAux = nodoAux->proximo;
			}
			
			resultado.push_back(enlaces.front());
			pop_heap(enlaces.begin(), enlaces.end(), trd_order);
			enlaces.pop_back();
		} else {
			pop_heap(enlaces.begin(), enlaces.end(), trd_order);
			enlaces.pop_back();
		}
	}
	
	return resultado;
}


int elegir_raiz(list<Enlace> aristas, int cantServidores){
	vector<NodoArbol> nodos;
	list<int> hojas_actuales_y_futuras;
	list<int> hojas_futuras_y_actuales;
	bool actual_o_futuro(true);
	int nodosRestantes = cantServidores;
	
	int i;
	
	for(i = 0; i < cantServidores; i++){ // O(N)
		NodoArbol nodo;
		nodo.numero = i;
		nodo.grado = 0;
		nodo.estoyEliminado = false;
		nodos.push_back(nodo);
	}
	
	int cantAristas = aristas.size();
	
	for(i = 0; i < cantAristas; i++){ // O(M)
		nodos[aristas.front().primer_servidor - 1].adyacencias.push_back(aristas.front().segundo_servidor);
		nodos[aristas.front().primer_servidor - 1].grado++;
		nodos[aristas.front().segundo_servidor - 1].adyacencias.push_back(aristas.front().primer_servidor);
		nodos[aristas.front().segundo_servidor - 1].grado++;
		aristas.pop_front();
	}
	
	for(i = 0; i < cantServidores; i++){ // O(N)		
		if(nodos[i].grado == 1){
			hojas_actuales_y_futuras.push_back(nodos[i].numero);
		}	
	}

	int padre;
	int padreAux;
	int cantAdyacencias;
	int cantHojas;

	while(nodosRestantes > 2) {
		if(actual_o_futuro) {
			
			//Tomo una hoja
			cantHojas = hojas_actuales_y_futuras.size();

			for(i = 0; i < cantHojas; i++) { // O(N)
				
				//Me fijo cual es el padre
				cantAdyacencias = nodos[hojas_actuales_y_futuras.front()].adyacencias.size();
				list<int>::iterator it = nodos[hojas_actuales_y_futuras.front()].adyacencias.begin();
				
				while(it != nodos[hojas_actuales_y_futuras.front()].adyacencias.end()) {
					if(!(nodos[(*it)-1].estoyEliminado)) {
						padre = *it;
						break;
					}
					it++;
				}
				
				//Le resto uno al grado del padre
				nodos[padre-1].grado--;
				//Si al restarle uno al grado lo convertí en hoja, lo agrego a la otra lista
				if(nodos[padre-1].grado == 1){
					hojas_futuras_y_actuales.push_back(nodos[padre-1].numero);
				}
				//Elimino la hoja
				nodos[hojas_actuales_y_futuras.front()].estoyEliminado = true;
				
				//La saco de la lista
				hojas_actuales_y_futuras.pop_front();
				//Resto uno a la variable de nodos eliminados
				nodosRestantes--;
			
			}
			
			//Cambio de lista
			actual_o_futuro = false;
			
		} else {
			cantHojas = hojas_futuras_y_actuales.size();
			
			for(i = 0; i < cantHojas; i++) {
				cantAdyacencias = nodos[hojas_futuras_y_actuales.front()].adyacencias.size();
				list<int>::iterator it2 = nodos[hojas_futuras_y_actuales.front()].adyacencias.begin();
				
				while(it2 != nodos[hojas_futuras_y_actuales.front()].adyacencias.end()) {
					if(!(nodos[(*it2)-1].estoyEliminado)) {
						padre = *it2;
						break;
					}
					it2++;
				}
				
				nodos[padre-1].grado--;
				if(nodos[padre-1].grado == 1){
					hojas_actuales_y_futuras.push_back(nodos[padre-1].numero);
				}
				nodos[hojas_futuras_y_actuales.front()].estoyEliminado = true;
				hojas_futuras_y_actuales.pop_front();
				nodosRestantes--;
			}
			actual_o_futuro = true;
		}
	}
	
	
	list<int>::iterator it3;
	if(actual_o_futuro) {
		return hojas_actuales_y_futuras.front()+1;
	} else {
		return hojas_futuras_y_actuales.front()+1;
	}
}

bool trd_order(Enlace e1, Enlace e2) {
	return (e1.costo > e2.costo);
}
	
ostream& operator<<(ostream &os, pair<list<Enlace>, int> enlaces) {
	int costo_total = 0;
	int tam = enlaces.first.size();
	list<Enlace>::iterator it = enlaces.first.begin();

	for (int a=0; a < tam; a++) {
		costo_total = costo_total + (*it).costo;
		it++;
	}

	it = enlaces.first.begin();
	os << costo_total << " ";
	os << enlaces.second << " ";
	os << tam << " ";
	for(int b = 0; b < tam; b++){
		os << (*it).primer_servidor << " " << (*it).segundo_servidor << " ";
		it++;
	}
	
	
	
	os << endl;
}
